A number of global illumination techniques for generating three dimensional computer graphics are known, the most common of which are ray tracing and radiosity. Both ray tracing and radiosity compute the global illumination of a scene by testing for intersections between (i) surface elements ("polygons") and/or boxes ("bounding volumes") derived from objects to be rendered in the scene, and (ii) rays cast from either viewpoints of the scene (ray tracing) or light sources in the scene (radiosity). These steps are sometimes referred to as polygon testing, box testing and/or shadow testing. The following publications which are incorporated herein by reference are descriptive of ray tracing and radiosity techniques for solving global illumination of a scene: An Introduction to Ray Tracing, Ed. by Andrew S. Glassnet, Academic Press, 1989 (chapter 2, pp. 33-77); Kay, T. L. et al., "Ray Tracing Complex Scenes," SIGGRAPH Proceedings, vol. 20, no. 4, pp. 269-277 (August, 1986); Greenberg, D. P. et al., "Radiosity: A Method For Computing Global Illumination," The Visual Computer, vol. 2, pp. 291-297 (1986); Cohen, M. F. et al., "The Hemi-Cube: A Radiosity Solution For Complex Environments," SIGGRAPH Proceedings, vol. 19, no. 3, pp. 31-40 (1985). One presently preferred method of solving the global illumination of the scene, and in which the present invention has particular application, is described in co-pending U.S. application Ser. No. 332,777 filed Apr. 3, 1989, now U.S. Pat. No. 5,313,568, and entitled, "Three Dimensional Computer Graphics Employing Ray Tracing to Compute Form Factors in Radiosity." See also, Wallace, J. R. et al., "A Ray Tracing Algorithm for Progressive Radiosity," SIGGRAPH Proceedings, Computer Graphics, vol. 23, no. 3, pp. 315-324 (July, 1989).
Typically, data defining the scene to be rendered, including a description of objects and light sources in the scene, are provided in a database upon which the global renderer operates (e.g., by ray tracing or radiosity) to compute global illumination, and generally all of the computations, including the ray intersection calculation, are carried out in a host computer. One of the problems with prior art global renderers, however, is that the ray intersecting calculations are extremely time consuming; most of the time spent solving global illumination is performed on the ray intersection calculations. The following publications generally discuss hardware and software systems for accelerating the global illumination solution: Potmesil, M. et al., "The Pixel Machine: A Parallel Image Computer," SIGGRAPH Proceedings, vol. 23, no. 3, pp. 69-78 (July, 1989); Akeley K. et al., "High-Performance Polygon Rendering," SIGGRAPH Proceedings, vol. 22, no. 4, pp. 239-246 (August, 1988). These systems, however, do not adequately address the need for accelerating ray intersection calculation in global rendering.
It is desirable to provide a method and apparatus that may be employed with either ray tracing or radiosity (or any other global illumination technique that relies upon ray intersections) for accelerating the ray intersection calculations, but is simple, efficient and relatively inexpensive to implement. The present invention achieves these goals.